package class02;

import java.util.HashMap;

public class Code04_CopyListWithRandom {
    static class Node {
        int value;
        Node next;
        Node ramdom;

        Node(int value) {
            this.value = value;
        }


    }


    public static Node copyRandomList1(Node head) {
        if (null == head) {
            return null;
        }
        // 注意此时map 中是node 类型，而不是数值类型
        HashMap<Node, Node> map = new HashMap<Node, Node>();

        Node cur = head;
        while (null != cur) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        cur = head;
        while (null != cur) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).ramdom = map.get(cur.ramdom);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 遍历链表，并且复制每个节点并插入链表中
     *
     * @param head
     * @return
     */
    public static Node copyRandomList2(Node head) {
        if (null == head) {
            return null;
        }
        Node cur = head;
        Node next;
        // 复制新链表节点并插入老链表
        while (null != cur) {
            next = cur.next;
            Node cpNode = new Node(cur.value);
            cur.next = cpNode;
            cpNode.next = next;
            cur = next;
        }
        // 复制random 指针
        cur = head;
        while (null != cur) {
            next = cur.next.next;
            cur.next.ramdom = cur.ramdom != null ? cur.ramdom.next : null;
            cur = next;
        }

        // 将新老节点拆分
        Node res = head.next;// 779911
        cur = head;
        Node copy;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }


        return res;

    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head1 = new Node(7);
        Node node = new Node(9);
        Node node2 = new Node(1);
        head1.next = node;
        node.next = node2;

        head1.ramdom = node2;
        node2.ramdom = node;
        node.ramdom = head1;
        printLinkedList(copyRandomList2(head1));
        ;
    }

}
